#include <stdio.h>

/*
 * 循环与递归
 *
 *		循环是有去无回，而递归则是有去有回(因为存在终止条件)。
 *
 *	递归调用之前的语句是从上到下的，函数调用之后的语句呢是从下到上的，因为后面的语句要等最下层或者最里面最后调用的那个
 *	函数执行之后不再调用了开始执行，然后返回上一层的时候再执行上一层函数调用后面的语句。并且特别注意的是，
 *	每次函数返回后直接就是函数调用后面的语句。
 *
 *	调用是一层一层往下，退回的顺序是调用顺序的逆序，逆序时输出结果
 */

/*
 *	递归有两个基本要素：
 *
 *		（1）边界条件：确定递归到何时终止，也称为递归出口。
 *
 *		（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果 
 *
 *	在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，
 *	首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。
 *
 *	一个递归函数的调用过程类似于多个函数的嵌套的调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，
 *	系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：
 *
 *		（1）运动开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
 *
 *		（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；
 *
 *		（3）每次递归调用结束后，将栈顶元
 */



/* 
 * 阶乘 n! 
 *		  
 *		  |	1		n = 0
 *   n! = |
 *		  | n*(n-1)	n > 0
 *
 *		120				24
 *	factorial(5) = 5 * factorial(4)
 *			24				6
 *		factorial(4) = 4 * factorial(3)
 *				6					2
 *			factorial(3) = 3 * factorial(2)
 *					2					1
 *				factorial(2) = 2 * factorial(1)
 *						1				1
 *					factorial(1) = 1 * factorial(0)
 */

int factorial(n)
{
	if (0 == n)
		return 1;
	else
		return n * factorial(n-1);
}

/*
 * 斐波那契
 * 
 *		   | 0, n = 0
 *	F(n) = | 1, n = 1
 *		   | F(n-1) + F(n-2), n > 1
 *
 *	5			3			2
 *	fib(5) = fib(5 - 1) + fib(5 - 2)
 *		3			2			1	
 *		fib(4) = fib(4 - 1) + fib(4 - 2)
 *			2			1			1
 *			fib(3) = fib(3 - 1) + fib(3 - 2)
 *				 1		  1			   0		
 *				fib(2) = fib(2 - 1) + fib(2 - 2)
 *
 *					fib(1) = 1
 *
 *						fib(0) = 0
 */
int fib(int i)
{
	if (i < 2) 
		return i == 0 ? 0 : 1;

	return fib(i - 1) + fib(i - 2);
}
//https://www.bilibili.com/video/BV1os41117Fs?p=32

/* 
 * 迭代实现 斐波那契 
 */
void fib_die()
{
	int i;
	int a[40];

	a[0] = 0;
	a[1] = 1;

	for (i = 2; i < 40; i++) {
		a[i] = a[i - 1] + a[i - 2];
		printf("%d ", a[i]);
	}
}

/*
 * function : input "FishC"  ---> output "ChsiF"
 *
 *	input A			intput B		intput C		intput #
 *	|				|				|				|				
 *  \/				\/				\/				\/
 *	c_output		c_output		c_output		a == '#'
 *	|				|				|				|				
 *  \/		  		\/				\/				\/
 *	output A	 	output B		output C		a == '#'
 *
 */
void c_output()
{
	char a;

	scanf("%c", &a);

	if (a != '#') 
		c_output();

	if (a != '#')
		printf("%c", a);
}

int main()
{
	//factorial(5);		// 120
	//printf("%d\n", fib(5));
	//fib_die(5);

	c_output();
	
	return 0;
}



